package 双指针.二分查找;
/*
解题思路：
    这题一看到“你的算法时间复杂度必须是 O(log n) 级别。”就知道应该用二分查找，本题的难点不是找到
    target，而是找到target后还要判断找到的target的前后是否还有别的target，因为题目求的是target的
    起始和结束位置。具体思路没啥好说的，就在代码注释一看就懂了。
 */
public class 在排序数组中查找元素的第一个和最后一个位置_34 {
    public static void main(String[] args) {
        int[] nums = new int[]{1};
        int target = 1;
        System.out.println(new 在排序数组中查找元素的第一个和最后一个位置_34().searchRange(nums, target));
    }


    public int[] searchRange(int[] nums, int target) {
        int find = searchRangeHelper(nums, target);
        //如果没找到，返回{-1, -1}
        if (find == -1){
            return new int[]{-1, -1};
        }

        int left = find - 1;
        int right = find + 1;
        //查看前面是否还有target
        while (left >= 0 && nums[left] == target) {
            left--;
        }
        //查看后面是否还有target
        while (right < nums.length && nums[right] == target) {
            right++;
        }

        /*
        简单理解，假如只有一个target，那么我们开始为了查找是否还有别的target而让left-1，right+1了，
        这时候却没有搜索到别的target，那么我们应该给left+1，right-1，来让它恢复原来的大小，再返回。
         */
        return new int[]{left + 1, right - 1};
    }

    //二分法查找
    public int searchRangeHelper(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
                /*找到了该目标值的地址，就将地址返回，但是要注意，再寻找一下还有没有其余的target，
                因为可能有多个target，但是题目要求的是target的起始、结束位置，比如[1,1,1,1]
                 */
            }
        }
        return -1;//如果没找到就返回-1
    }



      /* public int[] searchRange(int[] nums, int target) {
         int left = 0;
         int right = nums.length - 1;
         int[] result = new int[]{-1, -1};
         while (left <= right) {
             int mid = left + (right - left) / 2;

             if (nums.length == 1) {
                 if (nums[0] == target) {
                     result[0] = 0;
                     result[1] = 0;

                 }
                 break;
             } else if (nums[mid] < target) {
                 left = mid + 1;
             } else if (nums[mid] > target) {
                 right = mid - 1;
             } else {
                 if (mid==nums.length-1) {
                     result[0] = nums.length-1;
                     result[1] = nums.length-1;

                 } else if (nums[mid] == nums[mid + 1]) {
                     result[0] = mid;
                     result[1] = mid + 1;

                 } else if (mid == 0) {
                     result[0] = 0;
                     result[1] = 0;

                 } else if (nums[mid] == nums[mid - 1]) {
                     result[0] = mid - 1;
                     result[1] = mid;
                 }else{
                     result[0] = mid;
                     result[1] = mid;
                 }
                 left = right + 1;//已经找到了目标值，制造条件跳出循环
             }
         }
         return result;

     }*/
}
